package lib

import "strconv"

func init() {
	Probs = append(Probs, Problem{
		Num:         670,
		Discription: "交换数字中的两位数，使数字最大",
		Level:       2,
		Labels: map[string]int{
			"贪心":  1,
		},
	})
}

//左边交换的位置应该尽可能靠左，右边交换的数应尽可能靠右，换到左边的数应尽可能大
//从左往右遍历，维护一个当前的最大值、一对满足交换条件的左右索引
func MaximumSwap(num int) int {
	s := strconv.Itoa(num)
	rightMax := len(s) - 1
	left := -1
	right := -1
	for i := len(s) - 2; i >= 0; i-- {
		if s[i] > s[rightMax] {
			rightMax = i
		} else if s[i] < s[rightMax] {
			left = i
			right = rightMax
		}
	}

	if left == -1 {
		return num
	}

	strBytes := []byte(s)
	strBytes[left], strBytes[right] = strBytes[right], strBytes[left]
	res, _ := strconv.Atoi(string(strBytes))
	return res
}